package com.njupt.HashTable;

import java.util.ArrayList;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 */
public class GroupAnagrams {

    public boolean isAnagrams(String s1,String s2){
        if(s1.length()!=s2.length()){
            return false;
        }

        int[] nums = new int[26];
        for (int i = 0; i < s1.length(); i++) {
           nums[s1.charAt(i)-'a']++;
           nums[s2.charAt(i)-'a']--;
        }
        for (int num : nums){
            if(num!=0){
                return false;
            }
        }
        return true;

    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> lists = new ArrayList<>();

        if (strs.length==1){
            ArrayList<String> strings = new ArrayList<>();
            strings.add(strs[0]);
           lists.add(strings);
           return lists;
        }
        boolean isPut[] = new boolean[strs.length];
        isPut[0] = true;
        //处理第一个元素
        ArrayList<String> strings1 = new ArrayList<>();
        strings1.add(strs[0]);
        for (int i = 1; i < strs.length; i++) {
           if(isAnagrams(strs[0],strs[i])) {
               strings1.add(strs[i]);
               isPut[i] = true;
           }
        }
        lists.add(strings1);

        //处理第二个元素
        for (int i = 1; i < strs.length; i++) {
            if(!isPut[i]){
                ArrayList<String> strings = new ArrayList<>();
                strings.add(strs[i]);

                //如果最后一个元素没有被放进去
                if(i==strs.length-1){
                    lists.add(strings);
                    break;
                }

                for (int j = i+1; j < strs.length; j++) {
                    if(isAnagrams(strs[i],strs[j])){
                        strings.add(strs[j]);
                        isPut[j] = true;
                    }
                }
                lists.add(strings);
            }
        }
        return lists;
    }
    public static void main(String[] args) {


        String[] str = {"eat", "tea", "tan", "ate", "nat", "bat"};
        String[] str1 = {"a"};
        GroupAnagrams test = new GroupAnagrams();
        System.out.println(test.groupAnagrams(str1));
    }
}
